We report the discovery with XMM-Newton of correlated spectral and timing behavior in the ultraluminous X-ray source (ULX) NGC 5408 X-1. An approx. 100 ksec pointing with XMM/Newton obtained in January, 2008 reveals a strong 10 mHz QPO in the > 1 keV flux, as well as flat-topped, band limited noise breaking to a power law. The energy spectrum is again dominated by two components, a 0.16 keV thermal disk and a power-law with an index of approx. 2.5. These new measurements, combined with results from our previous January 2006 pointing in which we first detected QPOs, show for the first time in a ULX a pattern of spectral and temporal correlations strongly analogous to that seen in Galactic black hole sources, but at much higher X-ray luminosity and longer characteristic time-scales. We find that the QPO frequency is proportional to the inferred disk flux, while the QPO and broad-band noise amplitude (root mean squared, rms) are inversely proportional to the disk flux. Assuming that QPO frequency scales inversely with black hole mass at a given power-law spectral index we derive mass estimates using the observed QPO frequency - spectral index relations from five stellar-mass black hole systems with dynamical mass constraints. The results from all sources are consistent with a mass range for NGC 5408 X-1 from 1000 - 9000 Stellar mass. We argue that these are conservative limits, and a more likely range is from 2000 - 5000 Stellar mass. Moreover, the recent relation from Gierlinski et al. that relates black hole mass to the strength of variability at high frequencies (above the break in the power spectrum), and the variability plane results of McHardy et al. and Koerding et al., are also suggestive of such a. high mass for NGC 5408 X-1. Importantly, none of the above estimates appears consistent with a black hole mass less than approx. 1000 Stellar mass for NGC 5408 X-1. We argue that these new findings strongly support the conclusion that NGC 5408 X-1 harbors an intermediate mass black hole.